struct Solution;

impl Solution {
    //    pub fn path_in_zig_zag_tree(source: i32) -> Vec<i32> {
//        let mut sum = vec![];
//        sum.push(2);
//        let mut min = 1;
//        let mut max = 2;
//        let mut label = 1;
//        let target = source;
//        while target >= max {
//            label += 1;
//            min = max;
//            max = max << 1;
//            sum.push(min + max - 1);
//        }
//
//        // 确认对应位就是最这一层最小值加上最大值，减去现在的值
//        let mut target = source;
//        let mut result = vec![0; label];
//
//        // 先处理target 有可能是偶数层的假数
//        if label % 2 == 0 {
//            target = sum.get(label - 1).unwrap() - target;
//        }
//
//        for i in (1..=label).rev() {
//            // 奇数层正常，偶数层反过来
//            if i % 2 == 0 {
//                result[i - 1] = sum.pop().unwrap() - target;
//            } else {
//                sum.pop();
//                result[i - 1] = target;
//            }
//            target = target / 2;
//        }
//        result
//    }
    pub fn path_in_zig_zag_tree(source: i32) -> Vec<i32> {
        if source == 1 {
            return vec![source];
        }
        if source <= 3 {
            return vec![1, source];
        }
        let mut label = source as usize;
        let mut depth = (label as f64).log2() as usize;
        let mut vec = vec![0; depth + 1];
        vec[depth] = label as i32;
        let mut offset;
        while label > 1 {
            offset = (1 << (depth + 1)) - 1 - label as usize;
            label = ((1 << depth) + offset) / 2;
            depth -= 1;
            vec[depth] = label as i32;
        }
        vec
    }
}


fn main() {
    Solution::path_in_zig_zag_tree(0);
}
